/**
 * https://leetcode.cn/problems/count-the-number-of-good-nodes/submissions/582784100/
 * 3249.统计好节点的数目 1565
 * medium 陈贝纯 2024.11.24
 * dfs
 */

class Solution {
public:
    int ans=0;
    int dfs(int v,vector<vector<int>>& adj,vector<bool>& vist){
        vist[v]=false;
        int pre=-1,cnt=1,ok=1;
        for(auto num:adj[v]){
            if(vist[num]){
                int cur=dfs(num,adj,vist);
                cnt+=cur;
                if(pre<0)
                pre=cur;
                else if(pre!=cur)
                ok=0;
            }
        }
        ans+=ok;
        return cnt;
    }
    int countGoodNodes(vector<vector<int>>& edges) {
        int n=edges.size()+1;
        vector<vector<int>> adj(n);
        for(auto edge:edges){
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        vector<bool> vist(n,true);
        dfs(0,adj,vist);
        return ans;
    }
};